Problem 914 X of a Kind in a Deck of Cards
给定一个数组,判断该数组能否分成多个子数组,每个数组要求组内所有值相同,组间长度相同.
主要思路:
这个题目我的思路是判断每个数字的数量,如果发现全是偶数则正常返回,如果发现奇数,若剩下的全是该奇数的倍数即可.但是后来发现这就是求最大公约数的问题.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> groups = new HashMap<>();
for(int v : deck)
groups.put(v, groups.getOrDefault(v, 0)+1);
int gcd = -1;
for(int v : groups.values()){
if(gcd == -1)
gcd = v;
else{
gcd = gcd(gcd, v);
if(gcd == -1) break;
}
}
return gcd >= 2;
}
private int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b%a, a);
}
}
代码说明:
最大公约数可以通过辗转相除法求出.以(319,377)为例,取较大的那个对较小的那个取模,377%319=1…58,之后变成(319,58),继续319%58=5…29,之后变成(58,29)=2,余0,则返回29.最小公倍数可以通过两数相乘/最大公约数得到.
Problem 784 Letter Case Permutation
小写字母的全排列问题
主要思路:
当检测到字母的时候就进入递归,下标增加,当下标达到字符串长度时就加入list.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public List<String> letterCasePermutation(String S) {
List<String> strings = new ArrayList<>();
letterCasePermutation(S, S.toCharArray(), strings, 0);
return strings;
}
private void letterCasePermutation(String s, char[] chars, List<String> strings, int position) {
if (position == s.length()) {
strings.add(new String(chars));
return;
}
char ch = s.charAt(position);
if (Character.isLetter(ch)) {
chars[position] = Character.toLowerCase(ch);
letterCasePermutation(s, chars, strings, position+1);
chars[position] = Character.toUpperCase(ch);
}
letterCasePermutation(s, chars, strings, position+1);
}
}